package com.zdp.algorithm.stackandqueue;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * 汉诺塔问题 变种
 * 不能直接从左移动到右，需要经过右边
 * @author Zhengdp
 * @date 2023年01月08日 11:46
 */
@Slf4j
public class HanoiProblem {
    public static void main(String[] args) {
        HanoiProblemImpl hanoiProblem = new HanoiProblemImpl();
        hanoiProblem.leftRight(3);
    }
}

/**
 * 非递归方式实现 Hanoi塔
 *
 */
class HanoiProblemImpl2 extends HanoiProblemBase {
    private Stack<Integer> left = new Stack<>();
    private Stack<Integer> mid = new Stack<>();
    private Stack<Integer> right = new Stack<>();


}
@Slf4j
class HanoiProblemImpl extends HanoiProblemBase{
    /**
     * n 层 hanoi塔可以拆分为 1~n-1 与 n 层来看待
     * n层 ---> 1~n-1 移动到 Right
     *          n 移动到 Center
     *          1~n-1 移动到 LEFT
     *          n 移动到右边
     *     处理 n-1 层汉诺塔，步骤如上所示
     * leftRight(): 递归函数的含义：将n层的hanoi塔从Left移动到Right
     * rightLeft(): 递归函数的含义：将n层的hanoi塔从Right移动到Left
     * @param n n层hanoi塔
     */
    public void leftRight(int n) {
        if(n == 1){
            leftToRight(n);
            return ;
        }
        leftRight(n-1);
        leftMovCenter(n);
        rightLeft(n-1);
        centerMovRight(n);
        leftRight(n-1);
    }
    protected void rightLeft(int n){
        if(n == 1){
            rightToLeft(n);
            return ;
        }
        rightLeft(n -1);
        rightMovCenter(n);
        leftRight(n-1);
        centerMovLeft(n);
        rightLeft(n-1);
    }
}
@Slf4j
class HanoiProblemBase {

    /**
     * 左边移动到中间
     */
    protected void leftMovCenter(int n){
        log.info("Movie {} From Left TO Center",n);
    }

    /**
     * 从中间移动到右边
     */
    protected void centerMovRight(int n ) {
        log.info("Movie {} From Center TO Right",n);
    }

    /**
     * 从中间移动到左边
     */
    protected void centerMovLeft(int n ) {
        log.info("Movie {} From Center To Left",n);
    }

    /**
     * 从右边移动到中间
     */
    protected void rightMovCenter(int n ) {
        log.info("Movie {} From Right To Center",n);
    }

    /**
     * 从左边移动到右边
     */
    protected void leftToRight(int n ) {
        leftMovCenter(n);
        centerMovRight(n);
    }

    /**
     * 从右边移动到左边
     */
    protected void rightToLeft(int n){
        rightMovCenter(n);
        centerMovLeft(n);
    }

}
